package com.dyz.LeetCodeforSwordFingerOffer;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author: daiyizheng
 * @date: 2021/7/3 12:42
 * @description:
 */
public class MaxDepth55 {
    //DFS 递归调用
    int res = 0;
    public int maxDepth(TreeNode root) {
        if(root==null){return 0;}
        deepPath(root);
        return res;
    }
    private  void deepPath(TreeNode node){
        if(node==null){return;}
        if (node.left!=null){deepPath(node.left);}
        if(node.right!=null){deepPath(node.right);}
        res++;
    }
    //BFS ,使用两层队列
    public int maxDepth1(TreeNode root) {
        if(root==null){return 0;}
        Queue<TreeNode> queue = new LinkedList<>();//主队列
        queue.add(root);
        int res = 0; //计数
        while (!queue.isEmpty()){
            Queue<TreeNode> tmp = new LinkedList<>();//交换队列
            for(TreeNode node:queue){
                if(node.left!=null){tmp.add(node.left);}
                if(node.right!=null){tmp.add(node.right);}
            }
            //遍历完成后交换
            queue = tmp;
            res++;
        }
        return  res;
    }
}
